﻿#define _CRT_SECURE_NO_WARNINGS 1

//剑指Offer 52.两个链表的第—个公共节点
//https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    struct ListNode* p, * q;
//    int sizeA = 1, sizeB = 1;
//    if (!headA || !headB) return NULL;
//    //计算A和B的大小
//    for (p = headA; p->next != NULL; p = p->next, ++sizeA);
//    for (q = headB; q->next != NULL; q = q->next, ++sizeB);
//    p = headA;
//    q = headB;
//    //看A和B那个先走，有一个不会执行
//    for (int i = 0; i < sizeA - sizeB; i++, p = p->next);
//    for (int i = 0; i < sizeB - sizeA; i++, q = q->next);
//    //找到相同点
//    for (; p && q && p != q; p = p->next, q = q->next);
//    return p;
//}
/*
思路: 有两个指针指向A和B，当curA走完后跳到B上继续走，curB走完后跳到A上继续走
如果有共同结点，会在第一个共同结点相遇。
*/
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    struct ListNode* curA, * curB;
//    for (curA = headA, curB = headB; curA != curB;)
//    {
//        if (curA != NULL)
//        {
//            curA = curA->next;
//        }
//        else
//        {
//            curA = headB;
//        }
//        if (curB != NULL)
//        {
//            curB = curB->next;
//        }
//        else
//        {
//            curB = headA;
//        }
//    }
//    return curA;
//}





//剑指Offer 53-l.在排序数组中查找数字l
//https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
//int search(int* nums, int numsSize, int target)
//{
//    int i = 0;
//    int count = 0;
//    if (0 == numsSize) return 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (nums[i] == target)
//        {
//            ++count;
//        }
//    }
//    return count;
//}
// //二分思想
//int search(int* nums, int numsSize, int target)
//{
//    int left = 0, right = numsSize - 1, count = 0;
//    while (left <= right)
//    {
//        int mid = (left + right) / 2;
//        if (nums[mid] == target)
//        {
//			  //向左查找
//            for (int i = mid - 1; i >= 0 && (nums[i] == target); i--)
//            {
//                ++count;
//            }
//            //向右查找
//            for (int i = mid; i < numsSize && (nums[i] == target); i++)
//            {
//                ++count;
//            }
//            break;
//        }
//        else if (nums[mid] < target)
//        {
//            left = mid + 1;
//        }
//        else
//        {
//            right = mid - 1;
//        }
//    }
//    return count;
//}


//剑指Offer 53 - 11.0~n-1中缺失的数字
//https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
//int missingNumber(int* nums, int numsSize)
//{
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (nums[i] != i)
//        {
//            break;
//        }
//    }
//    return i;
//}
// //二分思想
//int missingNumber(int* nums, int numsSize)
//{
//    int left = 0, right = numsSize - 1;
//    while (left < right)
//    {
//        int mid = (left + right) / 2;
//        if (nums[mid] > mid)
//        {
//            right = mid - 1;
//        }
//        else if (nums[mid] == mid)
//        {
//            left = mid + 1;
//        }
//    }
//    if (nums[left] != left)
//    {
//        return left;
//    }
//    else
//    {
//        return right + 1;
//    }
//}



////暑假作业 Day-07
//HJ34图片整理
//https://www.nowcoder.com/practice/2de4127fda5e46858aa85d254af43941?tpId=37&&tqId=21257&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
//#include<stdio.h>
//#include<string.h>
//void bubble(char* str, int len)
//{
//    int i = 0, j = 0;
//    for (i = 0; i < len; i++)
//    {
//        for (j = 0; j < i; j++)
//        {
//            if (str[i] < str[j])
//            {
//                int tmp = str[i];
//                str[i] = str[j];
//                str[j] = tmp;
//            }
//        }
//    }
//}
//int main()
//{
//    char str[10001];
//    gets(str);
//    int len = strlen(str);
//    bubble(str, len);
//    printf("%s", str);
//    return 0;
//}


//724.寻找数组的中心下标
//https://leetcode.cn/problems/find-pivot-index/
//int pivotIndex(int* nums, int numsSize)
//{
//    int sum = 0, l_sum = 0;
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        sum += nums[i];
//    }
//
//    for (i = 0; i < numsSize; i++)
//    {
//        if (l_sum * 2 + nums[i] == sum)
//            return i;
//        else
//            l_sum += nums[i];
//    }
//    return -1;
//}